home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / freeWAIS-sf-1.1 / ir / stemmer.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-06-26  |  18.3 KB  |  558 lines
  1. /* WIDE AREA INFORMATION SERVER SOFTWARE:
  2.    No guarantees or restrictions.  See the readme file for the full standard
  3.    disclaimer.
  4.  
  5.    francois@welchgate.welch.jhu.edu
  6. */
  7.  
  8. /* Copyright (c) CNIDR (see ../COPYRIGHT) */
  9.  
  10.  
  11.  
  12. /* 
  13.  * stems a word.
  14.  * 
  15.  */
  16.  
  17. /* the main functions are:
  18.  *   stemmer
  19.  *
  20.  */
  21.  
  22. #include "cutil.h"
  23. #include <ctype.h> 
  24. #include "panic.h"  
  25. #include "futil.h"
  26. #include "stemmer.h"
  27.  
  28.  
  29.  
  30.  
  31. /* list words and their stemmed version in the log*/
  32. /* #define LIST_STEMS */
  33.  
  34.  
  35.  
  36.  
  37. char *
  38. stemmer (word)
  39. char *word;
  40. {
  41.  
  42. #ifdef LIST_STEMS
  43. /*
  44. ** - duplicate our word so that 
  45. **   we can provide a better listing
  46. */
  47.     char *word_copy;
  48.     
  49.     word_copy = s_malloc(strlen(word+5));
  50.     
  51.     strcpy(word_copy,word);
  52. #endif
  53.  
  54.  
  55. #ifdef STEM_WORDS
  56. /* not needed: tung
  57. if (!strcmp(word,"and") ||
  58.      (!strcmp(word,"not"))) {
  59.   return(word);
  60. }
  61. */
  62. Stem(word);
  63. #endif
  64. #ifdef LIST_STEMS
  65. /*
  66. ** - put up the original word and the stemmed version
  67. */
  68. waislog(WLOG_LOW, WLOG_INFO,"word: %s,  stemmed word: %s", word_copy, word); 
  69. s_free(word_copy);
  70. #endif
  71.  
  72. return(word);
  73.  
  74. }
  75.  
  76.  
  77. /*******************************   stem.c   ***********************************
  78.  
  79.    Purpose:    Implementation of the Porter stemming algorithm documented 
  80.                in: Porter, M.F., "An Algorithm For Suffix Stripping," 
  81.                Program 14 (3), July 1980, pp. 130-137.
  82.  
  83.    Provenance: Written by B. Frakes and C. Cox, 1986.
  84.                Changed by C. Fox, 1990.
  85.                   - made measure function a DFA
  86.                   - restructured structs
  87.                   - renamed functions and variables
  88.                   - restricted function and variable scopes
  89.                Changed by C. Fox, July, 1991.
  90.                   - added ANSI C declarations 
  91.                   - branch tested to 90% coverage
  92.  
  93.    Notes:      This code will make little sense without the the Porter
  94.                article.  The stemming function converts its input to
  95.                lower case.
  96. **/
  97.  
  98. /************************   Standard Include Files   *************************/
  99.  
  100. /* #include <stdio.h> */
  101.  
  102. /*****************************************************************************/
  103. /*****************   Private Defines and Data Structures   *******************/
  104.  
  105. #define EOS                         '\0'
  106.  
  107. #define IsVowel(c)        ('a'==(c)||'e'==(c)||'i'==(c)||'o'==(c)||'u'==(c))
  108.  
  109. typedef struct {
  110.            int id;                 /* returned if rule fired */
  111.            char *old_end;          /* suffix replaced */
  112.            char *new_end;          /* suffix replacement */
  113.            int old_offset;         /* from end of word to start of suffix */
  114.            int new_offset;         /* from beginning to end of new suffix */
  115.            int min_root_size;      /* min root word size for replacement */
  116.            int (*condition)();     /* the replacement test function */
  117.            } RuleList;
  118.  
  119. static char LAMBDA[1] = "";        /* the constant empty string */
  120. static char *end;                  /* pointer to the end of the word */
  121.  
  122. /*****************************************************************************/
  123. /********************   Private Function Declarations   **********************/
  124.  
  125. #ifdef __STDC__
  126.  
  127. static int WordSize( char *word );
  128. static int ContainsVowel( char *word );
  129. static int EndsWithCVC( char *word );
  130. static int AddAnE( char *word );
  131. static int RemoveAnE( char *word );
  132. static int ReplaceEnd( char *word, RuleList *rule );
  133.  
  134. #else
  135.  
  136. static int WordSize( /* word */ );
  137. static int ContainsVowel( /* word */ );
  138. static int EndsWithCVC( /* word */ );
  139. static int AddAnE( /* word */ );
  140. static int RemoveAnE( /* word */ );
  141. static int ReplaceEnd( /* word, rule */ );
  142.  
  143. #endif
  144.  
  145. /******************************************************************************/
  146. /*****************   Initialized Private Data Structures   ********************/
  147.  
  148. static RuleList step1a_rules[] =
  149.            {
  150.              101,  "sses",      "ss",    3,  1, -1,  NULL,
  151.              102,  "ies",       "i",     2,  0, -1,  NULL,
  152.              103,  "ss",        "ss",    1,  1, -1,  NULL,
  153.              104,  "s",         LAMBDA,  0, -1, -1,  NULL,
  154.              000,  NULL,        NULL,    0,  0,  0,  NULL,
  155.            };
  156.  
  157. static RuleList step1b_rules[] =
  158.            {
  159.              105,  "eed",       "ee",    2,  1,  0,  NULL,
  160.              106,  "ed",        LAMBDA,  1, -1, -1,  ContainsVowel,
  161.              107,  "ing",       LAMBDA,  2, -1, -1,  ContainsVowel,
  162.              000,  NULL,        NULL,    0,  0,  0,  NULL,
  163.            };
  164.  
  165. static RuleList step1b1_rules[] =
  166.            {
  167.              108,  "at",        "ate",   1,  2, -1,  NULL,
  168.              109,  "bl",        "ble",   1,  2, -1,  NULL,
  169.              110,  "iz",        "ize",   1,  2, -1,  NULL,
  170.              111,  "bb",        "b",     1,  0, -1,  NULL,
  171.              112,  "dd",        "d",     1,  0, -1,  NULL,
  172.              113,  "ff",        "f",     1,  0, -1,  NULL,
  173.              114,  "gg",        "g",     1,  0, -1,  NULL,
  174.              115,  "mm",        "m",     1,  0, -1,  NULL,
  175.              116,  "nn",        "n",     1,  0, -1,  NULL,
  176.              117,  "pp",        "p",     1,  0, -1,  NULL,
  177.              118,  "rr",        "r",     1,  0, -1,  NULL,
  178.              119,  "tt",        "t",     1,  0, -1,  NULL,
  179.              120,  "ww",        "w",     1,  0, -1,  NULL,
  180.              121,  "xx",        "x",     1,  0, -1,  NULL,
  181.              122,  LAMBDA,      "e",    -1,  0, -1,  AddAnE,
  182.              000,  NULL,        NULL,    0,  0,  0,  NULL,
  183.              };
  184.  
  185. static RuleList step1c_rules[] =
  186.            {
  187.              123,  "y",         "i",      0,  0, -1,  ContainsVowel,
  188.              000,  NULL,        NULL,    0,  0,  0,  NULL,
  189.            };
  190.  
  191. static RuleList step2_rules[] =
  192.            {
  193.              203,  "ational",   "ate",   6,  2,  0,  NULL,
  194.              204,  "tional",    "tion",  5,  3,  0,  NULL,
  195.              205,  "enci",      "ence",  3,  3,  0,  NULL,
  196.              206,  "anci",      "ance",  3,  3,  0,  NULL,
  197.              207,  "izer",      "ize",   3,  2,  0,  NULL,
  198.              208,  "abli",      "able",  3,  3,  0,  NULL,
  199.              209,  "alli",      "al",    3,  1,  0,  NULL,
  200.              210,  "entli",     "ent",   4,  2,  0,  NULL,
  201.              211,  "eli",       "e",     2,  0,  0,  NULL,
  202.              213,  "ousli",     "ous",   4,  2,  0,  NULL,
  203.              214,  "ization",   "ize",   6,  2,  0,  NULL,
  204.              215,  "ation",     "ate",   4,  2,  0,  NULL,
  205.              216,  "ator",      "ate",   3,  2,  0,  NULL,
  206.              217,  "alism",     "al",    4,  1,  0,  NULL,
  207.              218,  "iveness",   "ive",   6,  2,  0,  NULL,
  208.              219,  "fulnes",    "ful",   5,  2,  0,  NULL,
  209.              220,  "ousness",   "ous",   6,  2,  0,  NULL,
  210.              221,  "aliti",     "al",    4,  1,  0,  NULL,
  211.              222,  "iviti",     "ive",   4,  2,  0,  NULL,
  212.              223,  "biliti",    "ble",   5,  2,  0,  NULL,
  213.              000,  NULL,        NULL,    0,  0,  0,  NULL,
  214.            };
  215.  
  216. static RuleList step3_rules[] =
  217.            {
  218.              301,  "icate",     "ic",    4,  1,  0,  NULL,
  219.              302,  "ative",     LAMBDA,  4, -1,  0,  NULL,
  220.              303,  "alize",     "al",    4,  1,  0,  NULL,
  221.              304,  "iciti",     "ic",    4,  1,  0,  NULL,
  222.              305,  "ical",      "ic",    3,  1,  0,  NULL,
  223.              308,  "ful",       LAMBDA,  2, -1,  0,  NULL,
  224.              309,  "ness",      LAMBDA,  3, -1,  0,  NULL,
  225.              000,  NULL,        NULL,    0,  0,  0,  NULL,
  226.            };
  227.  
  228. static RuleList step4_rules[] =
  229.            {
  230.              401,  "al",        LAMBDA,  1, -1,  1,  NULL,
  231.              402,  "ance",      LAMBDA,  3, -1,  1,  NULL,
  232.              403,  "ence",      LAMBDA,  3, -1,  1,  NULL,
  233.              405,  "er",        LAMBDA,  1, -1,  1,  NULL,
  234.              406,  "ic",        LAMBDA,  1, -1,  1,  NULL,
  235.              407,  "able",      LAMBDA,  3, -1,  1,  NULL,
  236.              408,  "ible",      LAMBDA,  3, -1,  1,  NULL,
  237.              409,  "ant",       LAMBDA,  2, -1,  1,  NULL,
  238.              410,  "ement",     LAMBDA,  4, -1,  1,  NULL,
  239.              411,  "ment",      LAMBDA,  3, -1,  1,  NULL,
  240.              412,  "ent",       LAMBDA,  2, -1,  1,  NULL,
  241.              423,  "sion",      "s",     3,  0,  1,  NULL,
  242.              424,  "tion",      "t",     3,  0,  1,  NULL,
  243.              415,  "ou",        LAMBDA,  1, -1,  1,  NULL,
  244.              416,  "ism",       LAMBDA,  2, -1,  1,  NULL,
  245.              417,  "ate",       LAMBDA,  2, -1,  1,  NULL,
  246.              418,  "iti",       LAMBDA,  2, -1,  1,  NULL,
  247.              419,  "ous",       LAMBDA,  2, -1,  1,  NULL,
  248.              420,  "ive",       LAMBDA,  2, -1,  1,  NULL,
  249.              421,  "ize",       LAMBDA,  2, -1,  1,  NULL,
  250.              000,  NULL,        NULL,    0,  0,  0,  NULL,
  251.            };
  252.  
  253. static RuleList step5a_rules[] =
  254.            {
  255.              501,  "e",         LAMBDA,  0, -1,  1,  NULL,
  256.              502,  "e",         LAMBDA,  0, -1, -1,  RemoveAnE,
  257.              000,  NULL,        NULL,    0,  0,  0,  NULL,
  258.            };
  259.  
  260. static RuleList step5b_rules[] =
  261.            {
  262.              503,  "ll",        "l",     1,  0,  1,  NULL,
  263.              000,  NULL,        NULL,    0,  0,  0,  NULL,
  264.            };
  265.  
  266. /*****************************************************************************/
  267. /********************   Private Function Declarations   **********************/
  268.  
  269. /*FN***************************************************************************
  270.  
  271.        WordSize( word )
  272.  
  273.    Returns: int -- a weird count of word size in adjusted syllables
  274.  
  275.    Purpose: Count syllables in a special way:  count the number 
  276.             vowel-consonant pairs in a word, disregarding initial 
  277.             consonants and final vowels.  The letter "y" counts as a
  278.             consonant at the beginning of a word and when it has a vowel
  279.             in front of it; otherwise (when it follows a consonant) it
  280.             is treated as a vowel.  For example, the WordSize of "cat" 
  281.             is 1, of "any" is 1, of "amount" is 2, of "anything" is 3.
  282.  
  283.    Plan:    Run a DFA to compute the word size
  284.  
  285.    Notes:   The easiest and fastest way to compute this funny measure is
  286.             with a finite state machine.  The initial state 0 checks
  287.             the first letter.  If it is a vowel, then the machine changes
  288.             to state 1, which is the "last letter was a vowel" state.
  289.             If the first letter is a consonant or y, then it changes
  290.             to state 2, the "last letter was a consonant state".  In
  291.             state 1, a y is treated as a consonant (since it follows
  292.             a vowel), but in state 2, y is treated as a vowel (since
  293.             it follows a consonant.  The result counter is incremented
  294.             on the transition from state 1 to state 2, since this
  295.             transition only occurs after a vowel-consonant pair, which
  296.             is what we are counting.
  297. **/
  298.  
  299. static int
  300. WordSize( word )
  301.    char *word;   /* in: word having its WordSize taken */
  302.    {
  303.    register int result;   /* WordSize of the word */
  304.    register int state;    /* current state in machine */
  305.  
  306.    result = 0;
  307.    state = 0;
  308.  
  309.                  /* Run a DFA to compute the word size */
  310.    while ( EOS != *word )
  311.       {
  312.       switch ( state )
  313.          {
  314.          case 0: state = (IsVowel(*word)) ? 1 : 2;
  315.                  break;
  316.          case 1: state = (IsVowel(*word)) ? 1 : 2;
  317.                  if ( 2 == state ) result++;
  318.                  break;
  319.          case 2: state = (IsVowel(*word) || ('y' == *word)) ? 1 : 2;
  320.                  break;
  321.          }
  322.       word++;
  323.       }
  324.  
  325.    return( result );
  326.  
  327.    } /* WordSize */
  328.  
  329. /*FN**************************************************************************
  330.  
  331.        ContainsVowel( word )
  332.  
  333.    Returns: int -- TRUE (1) if the word parameter contains a vowel,
  334.             FALSE (0) otherwise.
  335.  
  336.    Purpose: Some of the rewrite rules apply only to a root containing
  337.             a vowel, where a vowel is one of "aeiou" or y with a
  338.             consonant in front of it.
  339.  
  340.    Plan:    Obviously, under the definition of a vowel, a word contains
  341.             a vowel iff either its first letter is one of "aeiou", or
  342.             any of its other letters are "aeiouy".  The plan is to
  343.             test this condition.
  344.  
  345.    Notes:   None
  346. **/
  347.  
  348. static int
  349. ContainsVowel( word )
  350.    char *word;   /* in: buffer with word checked */
  351.    {
  352.  
  353.    if ( EOS == *word )
  354.       return( FALSE );
  355.    else
  356.       return( IsVowel(*word) || (NULL != strpbrk(word+1,"aeiouy")) );
  357.  
  358.  
  359.    } /* ContainsVowel */
  360.  
  361. /*FN**************************************************************************
  362.  
  363.        EndsWithCVC( word )
  364.  
  365.    Returns: int -- TRUE (1) if the current word ends with a
  366.             consonant-vowel-consonant combination, and the second
  367.             consonant is not w, x, or y, FALSE (0) otherwise.
  368.  
  369.    Purpose: Some of the rewrite rules apply only to a root with
  370.             this characteristic.
  371.  
  372.    Plan:    Look at the last three characters.
  373.  
  374.    Notes:   None
  375. **/
  376.  
  377. static int
  378. EndsWithCVC( word )
  379.    char *word;   /* in: buffer with the word checked */
  380.    {
  381.    int length;         /* for finding the last three characters */
  382.  
  383.    if ( (length = strlen(word)) < 2 )
  384.       return( FALSE );
  385.    else
  386.       {
  387.       end = word + length - 1;
  388.       return(    (NULL == strchr("aeiouwxy",*end--))      /* consonant */
  389.               && (NULL != strchr("aeiouy",  *end--))        /* vowel */
  390.               && (NULL == strchr("aeiou",   *end  )) );   /* consonant */
  391.       }
  392.  
  393.    } /* EndsWithCVC */
  394.  
  395. /*FN**************************************************************************
  396.  
  397.        AddAnE( word )
  398.  
  399.    Returns: int -- TRUE (1) if the current word meets special conditions
  400.             for adding an e.
  401.  
  402.    Purpose: Rule 122 applies only to a root with this characteristic.
  403.  
  404.    Plan:    Check for size of 1 and a consonant-vowel-consonant ending.
  405.  
  406.    Notes:   None
  407. **/
  408.  
  409. static int
  410. AddAnE( word )
  411.    char *word;
  412.    {
  413.  
  414.    return( (1 == WordSize(word)) && EndsWithCVC(word) );
  415.  
  416.    } /* AddAnE */
  417.  
  418. /*FN**************************************************************************
  419.  
  420.        RemoveAnE( word )
  421.  
  422.    Returns: int -- TRUE (1) if the current word meets special conditions
  423.             for removing an e.
  424.  
  425.    Purpose: Rule 502 applies only to a root with this characteristic.
  426.  
  427.    Plan:    Check for size of 1 and no consonant-vowel-consonant ending.
  428.  
  429.    Notes:   None
  430. **/
  431.  
  432. static int
  433. RemoveAnE( word )
  434.    char *word;
  435.    {
  436.  
  437.    return( (1 == WordSize(word)) && !EndsWithCVC(word) );
  438.  
  439.    } /* RemoveAnE */
  440.  
  441. /*FN**************************************************************************
  442.  
  443.        ReplaceEnd( word, rule )
  444.  
  445.    Returns: int -- the id for the rule fired, 0 is none is fired
  446.  
  447.    Purpose: Apply a set of rules to replace the suffix of a word
  448.  
  449.    Plan:    Loop through the rule set until a match meeting all conditions
  450.             is found.  If a rule fires, return its id, otherwise return 0.
  451.             Connditions on the length of the root are checked as part of this
  452.             function's processing because this check is so often made.
  453.  
  454.    Notes:   This is the main routine driving the stemmer.  It goes through
  455.             a set of suffix replacement rules looking for a match on the
  456.             current suffix.  When it finds one, if the root of the word
  457.             is long enough, and it meets whatever other conditions are
  458.             required, then the suffix is replaced, and the function returns.
  459. **/
  460.  
  461. static int
  462. ReplaceEnd( word, rule )
  463.    char *word;        /* in/out: buffer with the stemmed word */
  464.    RuleList *rule;    /* in: data structure with replacement rules */
  465.    {
  466.    register char *ending;   /* set to start of possible stemmed suffix */
  467.    char tmp_ch;             /* save replaced character when testing */
  468.  
  469.    while ( 0 != rule->id )
  470.       {
  471.       ending = end - rule->old_offset;
  472.       if ( word <= ending )
  473.          if ( 0 == strcmp(ending,rule->old_end) )
  474.             {
  475.             tmp_ch = *ending;
  476.             *ending = EOS;
  477.             if ( rule->min_root_size < WordSize(word) )
  478.                if ( !rule->condition || (*rule->condition)(word) )
  479.                   {
  480.                   (void)strcat( word, rule->new_end );
  481.                   end = ending + rule->new_offset;
  482.                   break;
  483.                   }
  484.             *ending = tmp_ch;
  485.             }
  486.       rule++;
  487.       }
  488.  
  489.    return( rule->id );
  490.  
  491.    } /* ReplaceEnd */
  492.  
  493. /*****************************************************************************/
  494. /*********************   Public Function Declarations   **********************/
  495.  
  496. /*FN***************************************************************************
  497.  
  498.        Stem( word )
  499.  
  500.    Returns: int -- FALSE (0) if the word contains non-alphabetic characters
  501.             and hence is not stemmed, TRUE (1) otherwise
  502.  
  503.    Purpose: Stem a word
  504.  
  505.    Plan:    Part 1: Check to ensure the word is all alphabetic
  506.             Part 2: Run through the Porter algorithm
  507.             Part 3: Return an indication of successful stemming
  508.  
  509.    Notes:   This function implements the Porter stemming algorithm, with
  510.             a few additions here and there.  See:
  511.  
  512.                Porter, M.F., "An Algorithm For Suffix Stripping,"
  513.                Program 14 (3), July 1980, pp. 130-137.
  514.  
  515.             Porter's algorithm is an ad hoc set of rewrite rules with
  516.             various conditions on rule firing.  The terminology of
  517.             "step 1a" and so on, is taken directly from Porter's
  518.             article, which unfortunately gives almost no justification
  519.             for the various steps.  Thus this function more or less
  520.             faithfully refects the opaque presentation in the article.
  521.             Changes from the article amount to a few additions to the
  522.             rewrite rules;  these are marked in the RuleList data
  523.             structures with comments.
  524. **/
  525.  
  526. int
  527. Stem( word )
  528.    char *word;  /* in/out: the word stemmed */
  529.    {
  530.    int rule;    /* which rule is fired in replacing an end */
  531.  
  532.             /* Part 1: Check to ensure the word is all alphabetic */
  533.    for ( end = word; *end != EOS; end++ )
  534.       if ( !isalpha(*end) ) return( FALSE );
  535.       else *end = tolower( *end );
  536.    end--;
  537.  
  538.                 /*  Part 2: Run through the Porter algorithm */
  539.    (void)ReplaceEnd( word, step1a_rules );
  540.    rule = ReplaceEnd( word, step1b_rules );
  541.    if ( (106 == rule) || (107 == rule) )
  542.       (void)ReplaceEnd( word, step1b1_rules );
  543.    (void)ReplaceEnd( word, step1c_rules );
  544.  
  545.    (void)ReplaceEnd( word, step2_rules );
  546.  
  547.    (void)ReplaceEnd( word, step3_rules );
  548.  
  549.    (void)ReplaceEnd( word, step4_rules );
  550.  
  551.    (void)ReplaceEnd( word, step5a_rules );
  552.    (void)ReplaceEnd( word, step5b_rules );
  553.  
  554.            /* Part 3: Return an indication of successful stemming */
  555.    return( TRUE );
  556.  
  557.    } /* Stem */
  558.